package com.ShangGuiGu.sortAlgorithm.交换排序.插入排序;

/**
 * @auther zsj
 * @Date 2022/2/20
 *
 * 希尔排序是一种插入排序
 * 是对插入排序的优化版本
 * 也称为缩小增量排序
 *
 * gap的数量 == length/2
 * gap2的数量 == gap/2
 * ......
 * 直到 gap/2 =1时结束，并进行直接插入排序
 * 希尔排序是用一种公式分组进行，将组里的数据按照one by one 的方式进行制定规则来对比
 * 直到  number/2 =1时，就可以进行最有效的直接插入排序，避免了一个从小打大的排序规则时，最小的数字在最后造成的效率问题。
 **/
public class ShellSort {
    public static void main(String[] args) {

        int [] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSortMethod(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    /**
     *
     * @param n
     */
    static void shellSortMethod(int[] n){
        int temp = 0;//中转全局变量
        for (int gap = n.length/2; gap > 0; gap/=2){
            //for循环尽量不要一键生成，多自己去写写，会发现新天地
            //下面需要分组并且和指定length的数字进行比较并且交换
            for (int i = gap; i < n.length; i++) { // i = 步长   gap =组数  j =0 //是n[j]的数字和n[j + 5]数字的比
                for (int j = i -gap ; j>= 0; j-= gap) {
                    if (n[j] > n[j+gap]){
                        //说明这个数字是大于后面的数字的，交换位置
                        temp = n[j];
                        n[j]=n[j+gap];
                        n[j+gap]=temp;

                    }
                }
            }
        }

    }
}
